package HOT; /**
 * Author  zxy
 * Date  2023/6/16 下午 3:54
 */

/**
 * Definition for a binary tree node.
 * public class HOT.TreeNode {
 *     int val;
 *     HOT.TreeNode left;
 *     HOT.TreeNode right;
 *     HOT.TreeNode() {}
 *     HOT.TreeNode(int val) { this.val = val; }
 *     HOT.TreeNode(int val, HOT.TreeNode left, HOT.TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class MaxPathSum {
    private int ret = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {

        dfs(root);
        return ret;

    }

    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int left = Math.max(0, dfs(node.left));
        int right = Math.max(0, dfs(node.right));

        int cur = node.val + left + right;

        ret = Math.max(ret, cur);

        return node.val + Math.max(left, right);

    }
}
